# 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，
# 但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，
# 它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？


# 解题思路：就是从0，0开始，设置一个变量，看这个变量能累加多少次，也就是铺开多少个格子，同样需要设置一个矩阵保存上一步走过的bool
# 值得注意的是，这里就不只是需要上一步是否走过了，而是所有走过的都一直保留状态，这样可以剪枝最大化
# 否则，它可以一直死循环在两个格子中间移动，那是不对的
# threshold是k，还要自己设置一个矩阵，每一格存放m和n的各个位数相加之和
# 其实这里有两种想法，一个是不断累加一个变量，这个变量就是能走多少格子，另一个想法是所有走过的格子，都在矩阵中置为True，统计有多少个True
# 后一种可能比第一种安全，第一种可能会有重复的
class Solution:
    def __init__(self):
        self.matrix = None
        self.total = 0
        self.thresHold = 0

    def movingCount(self, threshold, rows, cols):
        # write code here
        self.thresHold = threshold
        self.matrix = [[0 for j in range(cols)] for i in range(rows)]

        self.gfs(threshold, rows, cols, 0, 0)
        return self.total

    def gfs(self, threshold, rows, cols, i, j):
        if i < 0 or j < 0:
            return
        if i >= rows or j >= cols:
            return
        if self.add_spical(i, j):
            return
        if self.matrix[i][j] != 0: return
        # 这一步很精妙，格子有三种状态：没走过：0，走过：1，不能走：-1
        if self.matrix[i][j] == -1 or self.add_spical(i, j):
            self.matrix[i][j] = -1
            return

        self.matrix[i][j] = 1
        self.total += 1
        self.gfs(threshold, rows, cols, i - 1, j)
        self.gfs(threshold, rows, cols, i + 1, j)
        self.gfs(threshold, rows, cols, i, j - 1)
        self.gfs(threshold, rows, cols, i, j + 1)

    def add_spical(self, x, y):
        my_list = sum(map(int, str(x) + str(y)))
        return my_list > self.thresHold
